package dongtaiguihua;

public class 跳台阶NC68 {

    public static void main(String[] args) {
//        System.out.println(jumpFloor(7));
    }

    // 1.递归
//    static int jumpFloor(int number) {
//        if (number <= 1) {
//            return 1;
//        }
//        return jumpFloor(number - 1) + jumpFloor(number - 2);
//    }

    // TODO
    //  可以发现，f(2)计算了两次，f(1)计算了3次，f(0)计算了2次。可以采用一个map存储已经被计算过的值

    //2.动态规划
    // f(0)=1,f(1)=1是动态规划的初始状态；
    // dp为一维数组，其中dp[i]的值代表青蛙跳第n个台阶的方法数；

//   static int jumpFloor(int number) {
//        vector<int> dp(number+1, 0);
//        // 初始状态
//        dp[0] = dp[1] = 1;
//        for (int i=2; i<=number; ++i) {
//            // 状态转移方程
//            dp[i] = dp[i-1] + dp[i-2];
//        }
//        return dp[number];
//    }
}
